Optimalizace mravenčí kolonií

Optimalizace mravenčí kolonií (v originále Ant Colony Optimization, používá se zkratka ACO) je meta-heuristická technika používaná v oboru umělé inteligence pro hledání přibližných řešení kombinatorických problémů. Technika se inspiruje v chování mravenců při hledání potravy. Řadíme ji mezi další metody využívající inteligence hejna. ACO, jakožto meta-heuristika, popisuje celou třídu algoritmů.

Algoritmus Ant System

Algoritmus Ant System (AS) lze z anglického originálu přeložit jako mravenčí systém. Jedná se o první algoritmus, který spadá do třídy ACO.

Algoritmus používá při výpočtu množinu agentů, mravenců. Hlavním znakem algoritmu je komunikace jednotlivých agentů skrze prostředí. Zde lze právě spatřit podobnost se skutečnými mravenci, kteří zanechávají feromonovou stopu na cestě k nalezené potravě. Právě takto nacházejí mravenci nejkratší cestu k potravě, protože čím delší cesta, tím rychleji pachová stopa vyprchá a stopa na kratší cestě převáží. Feromonová stopa pak slouží jako druh pozitivní zpětné vazby. Mravenec se s vyšší pravděpodobností rozhoduje pro cestu se silnější stopou. Poprvé tento postup popsal v roce 1991 Colorni, Dorigo a Maniezzo.^[1]

AS předpokládá, že řešení je rozdělitelné do jednotlivých komponent, kterých je konečný a rozumně omezený počet. Následuje popis AS tak jak ho uvádí Blum^[2] při použití na problém obchodního cestujícího (snažíme se najít v grafu nejkratší cestu, která projde všemi vrcholy právě jednou a skončí tam, kde začala - není to tedy přesně cesta, ale kružnice).

Popis algoritmu

Mějme tedy graf $G=(V,E)$ a váhy hran $c:E\mapsto \mathbb {R}$ , tedy formální reprezentaci mapy s městy, hranami mezi nimi a jejich cenami. Snažíme se nalézt nejkratší kružnici procházející každým vrcholem. Účelová funkce pro tento problém je tedy součet vah hran na kružnici. Jako reprezentaci částečného řešení budeme používat binární proměnnou $X_{e}$ pro každou hranu -- tedy zda hrana v částečném řešení je, nebo není. Hrany jsou tedy komponentami řešení. Ke každé hraně $e_{i,j}$ (hrana mezi vrcholy $i$ a $j$ ) si tedy budeme uchovávat sílu feromonové stopy $\tau _{i,j}$ . Úlohou každého mravence je konstrukce platného řešení, tedy platné kružnice v grafu.

Nejprve je vybrán jeden náhodný vrchol jako počátek. Mravenec poté postupně opakuje konstrukční krok, kdy si vybírá nějaké město, ve kterém ještě nebyl a posouvá se do něho z aktuálního města. Jakmile nezbývají žádné nepoužité vrcholy, mravenec se vrací do počátečního města. V důsledku si tedy mravenec uchovává svoji trasu $T$ . Pokud se tedy aktuálně mravenec nachází ve městě $v_{i}$ , pak pravděpodobnost, že se mravenec vydá do města $j$ je $P(e_{i,j})={\tau \over \sum _{k\in \{1\dots |V|\},k{\not \in }T}\tau _{i},k}$ , kde ${v_{j}{\not \in }T}$ .

Jakmile všichni mravenci ukončí konstrukční fázi, je nutné pozměnit hladiny feromonů na hranách. Nejprve se feromon odpaří: $\tau _{i,j}=\tau _{i,j}\cdot \rho$ , kde $\rho$ odpovídá koeficientu odpařování.

Poté se započítá feromonová stopa, kterou každý mravenec při procházení po hranách zanechal. Za každého mravence se tedy započte: $\tau _{i,j}=\tau _{i,j}+{Q \over f(s)}$ , kde $Q$ je nějaká kladná konstanta, $f$ je účelová funkce a $s$ je nalezené řešení daného mravence.

Tento postup však nikdy nezískal větší popularity, protože v době jeho vzniku už existovaly jiné, efektivnější algoritmy.

Konvergence

Haibin v roce 2010^[3] publikoval důkaz konvergence algoritmu při jeho aplikaci na problém obchodního cestujícího. V důkazu dochází k tvrzení, že při nekonečném počtu kroku je pravděpodobnost nalezení optimálního řešení rovna 1. Ačkoliv se v článku hovoří o ACO, jako celé meta-heuristice, v použitém značení u důkazu se nezmiňuje žádné zobecnění a hovoří se pouze o problému obchodního cestujícího.

Popis meta-heuristiky

Meta-heuristika poskytuje společný zobecněný popis všem algoritmům vycházející z této podobné myšlenky, a sice používání prostředí ke komunikaci mezi agenty s inspirací v chování mravenců. Následuje popis převzatý od autorů Doriga a Stützleho^[4].

Zjednodušeně lze meta-heuristiku rozdělit do tří fází: Vytváření řešení, Aktualizace feromonu a Vnější zásahy. Tyto tři fáze se nemusejí odehrávat postupně, ale naopak asynchronně a paralelně. Je pouze na volbě autora implementace, jaký přístup zvolí.

Vytváření řešení

V této fázi všichni mravenci paralelně a asynchronně procházejí sousedícími vrcholy konstrukčního grafu a postupně staví svá řešení. Využívají při tom feromonových stop a nějakých dodatečných heuristických informací o úloze (například v případě obchodního cestujícího můžeme upřednostňovat kratší hrany). Jakmile mravenec dokončí sestavování svého řešení, vyhodnotí ho (zjistí hodnotu účelové funkce pro toto řešení) a výsledná hodnota bude použita ve fázi aktualizace feromonu.

Aktualizace feromonu

Aktualizace feromonu upravuje intenzitu feromonových stop na použitých cestách v konstrukčním grafu. Intenzita feromonu se buď zvyšuje, nebo snižuje. Ke zvýšení typicky dochází, pokud je stopa používána mnoha mravenci. Ke značnému zvýšení ale může dojít i tedy, použije-li spojení jeden mravenec, který však najde velmi úspěšné řešení. Feromonová stopa tak zanechává ostatním mravencům informaci o preferované volbě.

Naopak intenzitu feromonu snižujeme v průběhu času, pokud tedy mravenci spojení používají málo nebo vůbec, preference této volby se postupně vytratí. Tento mechanismus představuje užitečnou formu zapomínání, která zabraňuje předčasné konvergenci do lokálních optim.

Vnější zásahy

Vnější zásahy slouží k provedení úprav výpočtu, které nelze provádět na úrovni mravence. Tato fáze není nutná, ale používá se k různým vylepšením řešení z globální perspektivy. Někdy se jedná se buď o dodatečné lokální hledání v okolí nalezených řešení. Může však jít i o zvýhodnění nejlepšího nalezeného řešení pomocí posílení jím použitých feromonových stop.

Související články

Reference

↑ Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies; European Conference on Artificial Life; str 134–142; 1991
↑ Blum, C.: Ant colony optimization: Introduction and recent trendsů; Physics of Life Reviews, 2(4); str. 353-373; 2005
↑ Haibin, D.: Ant Colony Optimization: Principle, Convergence and Application; Handbook of Swarm Intelligence; Springer Berlin Heidelberg 2010; ISBN 978-3-642-17390-5; str. 373-388; Doi: 10.1007/978-3-642-17390-5_16 [1]
↑ Dorigo, M., Stützle, T.: Ant Colony Optimization; MIT Press, Cambridge, MA; 2004; str. 37-38

[1] Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies; European Conference on Artificial Life; str 134–142; 1991

[2] Blum, C.: Ant colony optimization: Introduction and recent trendsů; Physics of Life Reviews, 2(4); str. 353-373; 2005

[3] Haibin, D.: Ant Colony Optimization: Principle, Convergence and Application; Handbook of Swarm Intelligence; Springer Berlin Heidelberg 2010; ISBN 978-3-642-17390-5; str. 373-388; Doi: 10.1007/978-3-642-17390-5_16 [1]

[4] Dorigo, M., Stützle, T.: Ant Colony Optimization; MIT Press, Cambridge, MA; 2004; str. 37-38

[1]

[2]

[3]

[4]